<!DOCTYPE HTML PUBLIC "-//w3c//dtd html 4.0 transitional//en">
<html><head>


   <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
   <meta name="description" content="What is the Median?">
   <meta name="keywords" content="htmlatex">
   <meta name="resource-type" content="document">
   <meta name="distribution" content="global">
   <meta name="GENERATOR" content="Mozilla/4.75 [en] (X11; U; Linux 2.2.16-22 i586) [Netscape]">
   <meta name="Author" content="Sadi Khan">
   <title>What is the Median?</title>
<!--Converted with LaTeX2HTML 98.1 release (February 19th, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by:  Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
  Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
</head><body bgcolor="#ffffff" lang="EN">

<center>
<h1>
</h1></center>
&nbsp;
<center><table bgcolor="#0060f0" border="0">
<tbody><tr>
<td><a name="SECTION0001000000000000000000"></a><b><font color="#c0ffff"><font size="+2">
What is the Median?&nbsp;</font></font></b></td>
</tr>
</tbody></table></center>
<h2>
<a name="SECTION0001002000000000000000"></a><font color="#0070e8">The Problem</font></h2>
Median plays an important role in the world of statistics. By definition,
it is a value which divides an array into two equal parts. In this problem
you are to determine the current median of some long integers.
<p>Suppose, we have five numbers {1,3,6,2,7}. In this case, 3 is the median
as it has exactly two numbers on its each side. {1,2} and {6,7}.
</p><p>If there are even number of values like {1,3,6,2,7,8}, only one value
cannot split this array into equal two parts, so we consider the average
of the middle values {3,6}. Thus, the median will be (3+6)/2 = 4.5. In
this problem, you have to print only the integer part, not the fractional.
As a result, according to this problem, the median will be 4!
</p><h2>
<a name="SECTION0001001000000000000000"></a><font color="#0070e8">Input&nbsp;</font></h2>
The input file consists of series of integers X ( 0 &lt;= X &lt; 2^31 )
and total number of integers N is less than 10000. The numbers may have
leading or trailing spaces.
<h2>
<a name="SECTION0001002000000000000000"></a><font color="#0070e8">Output&nbsp;</font></h2>
For each input print the current value of the median.

<h2>
<a name="SECTION0001003000000000000000"></a><font color="#0070e8">Sample
Input&nbsp;</font></h2>

<pre>1
3
4
60
70
50
2</pre>

<h2>
<a name="SECTION0001004000000000000000"></a><font color="#0070e8">Sample
Output&nbsp;</font></h2>

<pre>1
2
3
3
4
27
4</pre>

<hr>
<i>Sadi Khan<br>
2001-04-01</i>
</body></html>